package l.l.w.practice.EightQueens;

/**
 * Created by llw on 2017/9/4.
 */
public class EightQueensBit {
    public int num2(int n){
        if(n<1 || n>32){
            return 0;
        }
        int upperLim = n ==32?-1:(1<<n)-1;
        return process2(upperLim,0,0,0);
    }

    private int process2(int upperLim, int colLim, int leftDiaLim, int rightDiaLim) {
        if(colLim == upperLim){
            return 1;
        }
        int pos = 0;
        int mostRightOne = 0;
        pos = upperLim & (~(colLim | leftDiaLim | rightDiaLim));
        int res = 0;
        while(pos != 0){
            mostRightOne = pos & (~pos +1);
            pos = pos - mostRightOne;
            res += process2(upperLim,colLim | mostRightOne,(leftDiaLim | mostRightOne)<<1,(rightDiaLim | mostRightOne)>>>1);
        }
        return res;
    }


    public static void main(String[] args) {
        System.out.println("???");
        int num = 16;
        long start = System.currentTimeMillis();
        int count = new EightQueensBit().num2(num);
        long end = System.currentTimeMillis();
        System.out.println(count);
        System.out.println((end-start)/1000);
    }
}
